//
//  VerifyPostorder.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/27.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  剑指 Offer 33. 二叉搜索树的后序遍历序列

import UIKit

/*
 剑指 Offer 33. 二叉搜索树的后序遍历序列
 
 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

  

 参考以下这颗二叉搜索树：

      5
     / \
    2   6
   / \
  1   3
 示例 1：

 输入: [1,6,3,2,5]
 输出: false
 示例 2：

 输入: [1,3,2,6,5]
 输出: true
  

 提示：

 数组长度 <= 1000
 */

class VerifyPostorder: NSObject {
    
    /*后序遍历  按照二叉树的 前后中顺序进行遍历。
      二叉搜索树，根节点的左子树所有元素都小于根节点，所有右子树的元素都大于根节点
     
     
     假设给定的数组是二叉搜索树的后序遍历结果。
     数组最后一个元素就是根节点的值；
     从后往前数第一比根元素大的值就是右子树的根节点
     ···
     
     
     */
    func verifyPostorder(_ postorder: [Int]) -> Bool {

        return self.recur(0, postorder.count - 1, postorder)
    }
    
    func recur(_ i:Int, _ j:Int, _ postorder:[Int]) -> Bool{
        if i >= j{
            return true
        }
        
        var p = i
        while postorder[p] < postorder[j] {
            p += 1
        }
        
        let m = p
        while postorder[p] > postorder[j] {
            p += 1
        }
        return p == j && self.recur(i, m-1, postorder) && self.recur(m, j-1, postorder)
    }
}
